Greg Detre
@14:40 on Friday, October 04, 2002
the optional end question has not been posed to the CL community
Problems
verb subcategorisation
e.g. �frog met�, �frog slept a cookie�
agreement
�frog bake a cake�, �they bakes a cake�
Chomsky argued: you can�t have cross-talk in a CFG � that�s why they call them context-free
so how do you deal with these problems? let�s assume that it is CF, then what technical means should we add to CF?
one solution is just to make the non-terminal categories more finely-grained
quantify (e.g. (forAll num) S � NPnum VPnum)
this is just an abbreviation for enumerating the finite set of all expansions � not formally more powerful, but potentially exponentially more succinct
metarules
if you chain together [[V NP] (PP)] successively � need to be able to reason about the subcategories in your metalanguage(???)
all of these ideas depend on the idea that non-terminals cannot be atomic � they�re structured not primitive
could you use statistical methods to induce what the rules of the grammar must be?
Tricky constructions (discussed last week)
�Who ate the cookies?�
�Frog did bake her some cookies.�
�What did Frog eat?�
you can�t say �What did Frog sleep?� � even though there�s no NP after the verb, as usual, the same constraints apply to wh-constructions � how are you going to do that with a CFG?
you could employ a set of string rewrite rules that operate on pseudo-sentences generated by a CFG (e.g. �Did Frog eat what?�)
subjacency violation (e.g. �Frog said that who went to the store�) � need something more sophisticated that rewrites the rules/trees, not just the strings
transformational grammar: the base grammar builds the deep structure, and the transformations turn it into the surface structure
does this correspond to the way that we acquire language, that we first start to learn the things that have fewest transformations�
�Syntactic argumentation and the structure of English� � David Perlmutter
great if you want to learn linguistics without 112a and 112b � teaches structure of English as well as the methods by which linguists have reached them
Prolog
designed for the niche market of NLP
the general idea is: write down what you want to know, and let the system figure it out
P1 ^ P2 ^ Pk � N1 (u N2 u Nk)
N1 :- P1, � , Pk
theorem-proving with definite clauses is much easier
you can still write infinite loops
measure speed of Prolog systems in terms of logical inferences per second (rather than floating point operations per second) � original Prolog systems managed a handful per second � first efficient Prolog compiler in the late 70s/80, which could do thousands of logical inferences per second � millions nowadays
a term (const | var | fn(term, � term)) is the Prolog equivalent of a data structure
a list can be represented as a tree �.(1,.(2,.(3, [])))� � this is the same idea as Lisp (where you use cons instead of .)
.(1,.(2,X)) � for when you know only the first two elements of the list
resolution � negate what you want to prove
concatenation
concat( L, R, LR ).
concat( [], R, R ).
concat( [A], R, [A|R] ).���� this is entailed by preceding + succeeding
statements
concat([First | Rest], List, [First | RestList]) :-
concat (Rest, List, RestList).
it�s completely deterministic
for instance, it�ll give you all the possibilities for:
concat(X, Y, [1, 2, 3, 4])
the member predicate
memb(X,[X|_]).
memb(X,[_|L]):-
memb(X,L).
the reverse predicate
Dev
reverse([],[]).
reverse([X|Y],[Z|X]) :-
reverse([Y],[Z]).
Nora
reverse([],[]).
reverse([X|Resta],[Restb|X]) :-
reverse(Resta,Restb).
Noam
revappend([],L,L
�
Shieber1
rev([],[]).
rev([X|Y1], Res) :-
rev(Y1, Y2),
concat(Y2, [X], Res).
Shieber2
rev(X, Y) :-
rev(X, Y, []).
rev([], Y, Y).
rev([A|RestA], Y, Z) :-
rev(RestA, Y, [A|Z]).
when you try rev(X, [3,2,1]), then the program goes into an infinite loop after it gets the first match (because it doesn�t know that X and Y should be of equal length)
the information from the callee and the caller flows in both directions in Prolog (unlike C and Lisp)
any language in which you can�t write an infinite loop is not an interesting language (Church�s thesis)
:- op(1200, xfx, �==>�)����� defines an operator???
ensure_loaded � loads a file
parsing
�???
encode string position in terms of the list of things that follow it (ending with the empty list)
e.g. connects(a, [a, cookie], [cookie]).
in general: connects(W, [W|Rest], Rest).
now you can ask things like:
s([frog, baked, every, cookie],[]).
define a unary s, so you don�t have to have the empty list at the end
s(String) :- s(String,[]).
then you can do things like:
s([X,met,Y]).
to get: X = frog, Y = toad, and permutations thereof
write an interpreter for an arbitrary grammar
rule(s, [np, vp] ).
s ==> [np, vp].
need to write some code that would interpret those clauses
parse(Sym, P0, P, T).�������� some symbol, string, tree output
parse(W, P0, P) :-
connects(W, P0, P).
parse(N, P0, P) :-
N ==> RHS,
parse(RHS, P0, P).
but then you�ve got RHS (which is a list) rather than a symbol (Sym), so�
parse([], P0, P0).
parse[Sym|Rest], P0, P) :-
parse(Sym, P0, P1)
parse(Rest, P1, P).
�???
can parse any CFG in CFG notation with just a few lines of Prolog code
ask if lectures will be online
optional question???
what can you say in second order formal logic that you can�t in first-order???
is a definite clause the same as a Horn clause???
in a definite/Horn clause, can you swap round the Ps and Ns???
why do you use the underscore (the anonymous variable) instead of just a bunch of different variables???
what type of language/grammar wouldn�t be able to write an infinite loop??? can a regular language go into an infinite loop???
connects, P, P0, P1???